Search for: All records

The metabolic activity of microbial communities is essential for host and environmental health, influencing processes from immune regulation to bioremediation. Given this importance, the rational design of microbiomes with targeted functional properties is an important objective. Designing microbial consortia with targeted functions is challenging due to complex community interactions and environmental heterogeneity. Community-function landscapes address this challenge by statistically inferring impacts of species presence or absence on function. Similar to fitness landscapes, community-function landscapes are shaped by both additive effects and interactions (epistasis) among species that influence function. Here, we apply the community-function landscape approach to design synthetic microbial consortia to degrade the toxic environmental contaminant bisphenol-A (BPA). Using synthetic communities of BPA-degrading isolates, we map community-function landscapes across increasing BPA concentrations, where higher BPA means greater toxicity. As toxicity increases, so does epistasis, indicating that collective effects become more important in degradation. Further, we leverage landscapes to rationally design communities with predictable BPA degradation dynamics in vitro. Remarkably, designed synthetic communities are able to remediate BPA in contaminated soils. Our results demonstrate that toxicity can drive epistatic interactions in community-function landscapes and that these landscapes can guide microbial consortia design for bioremediation. 

Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a superlinearly convergent subgradient method? We provide a positive answer to this question for a broad class of sharp semismooth functions. Funding: The research of D. Davis was supported by the Division of Mathematical Sciences [Grant 2047637] and the Alfred P. Sloan Foundation. 

Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called geometric step decay and proceeds by halving the step size after every few epochs. In recent work, geometric step decay was shown to improve exponentially upon classical sublinear rates for the class of sharp convex functions. In this work, we ask whether geometric step decay similarly improves stochastic algorithms for the class of sharp weakly convex problems. Such losses feature in modern statistical recovery problems and lead to a new challenge not present in the convex setting: the region of convergence is local, so one must bound the probability of escape. Our main result shows that for a large class of stochastic, sharp, nonsmooth, and nonconvex problems a geometric step decay schedule endows well-known algorithms with a local linear (or nearly linear) rate of convergence to global minimizers. This guarantee applies to the stochastic projected subgradient, proximal point, and prox-linear algorithms. As an application of our main result, we analyze two statistical recovery tasks—phase retrieval and blind deconvolution—and match the best known guarantees under Gaussian measurement models and establish new guarantees under heavy-tailed distributions. 

Abstract We consider the task of recovering a pair of vectors from a set of rank one bilinear measurements, possibly corrupted by noise. Most notably, the problem of robust blind deconvolution can be modeled in this way. We consider a natural nonsmooth formulation of the rank one bilinear sensing problem and show that its moduli of weak convexity, sharpness and Lipschitz continuity are all dimension independent, under favorable statistical assumptions. This phenomenon persists even when up to half of the measurements are corrupted by noise. Consequently, standard algorithms, such as the subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within a constant relative error of the solution. We complete the paper with a new initialization strategy, complementing the local search algorithms. The initialization procedure is both provably efficient and robust to outlying measurements. Numerical experiments, on both simulated and real data, illustrate the developed theory and methods.